#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> ans;
        TreeNode* cur = root;
        while (cur || !st.empty()) {
            while (cur) {
                st.push(cur);
                ans.push_back(cur->val);
                cur = cur->left;
            }
            cur = st.top();
            st.pop();
            cur = cur->right;
        }


        return ans;
    }
};